//
//  Problem1081.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/27.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1081. 不同字符的最小子序列
 返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

 示例 1：
     输入：s = "bcabc"
     输出："abc"
 示例 2：
     输入：s = "cbacdcbc"
     输出："acdb"
 提示：
     1 <= s.length <= 1000
     s 由小写英文字母组成
 */
@objcMembers class Problem1081: NSObject {
    func solution() {
        print(smallestSubsequence("bcabc"))
        print(smallestSubsequence("cbacdcbc"))
        print(smallestSubsequence("baababaaaaababbbbbbaababaababa"))    // ab
        print(smallestSubsequence("cbaacabcaaccaacababa"))  // abc
    }
    /*
     一个字符串，删除一个字符后，刚刚比现在小
     1: 如果字符是递增的: abc 那么删除最后一个字符c => ab
     2: 如果字符是递减的: cba 那么删除是第一个字符c => ba
     3: 复杂一点：先递增后递减 abcba, 删除的还是字符c，因为比现在刚刚小，那么尽量删除递增的最后一个，递减的第一个
     4: 先递减后递增 cbabc, 删除的还是第一个字符c，例如： babc cabc cbac cbab
     我们总结出来：删除一个字符，肯定是删除递减的第一个字符，如果不存在，删除递增的最后一个字符
     那么我们要做的就是不断执行上面的上面，我们需要特殊处理的是：“所有不同字符，且只包含一次”，所以在我们判断是否删除这个字符时：如果这个字符后面没有出现过，那么这个字符就不能删除了
     1: 如果这个字符后面没有出现过，那么这个字符就不能删除了 => 为了判断后面这个字符是否还有，我们需要先统计每一个字符的个数
     2: 如果这个字符，已经在前面存储过了，那么这个过滤这个字符 => 每次存储时，先-1，然后变成负数
     
     */
    func smallestSubsequence(_ s: String) -> String {
        // 统计每个字符存在的次数
        var nlist:[Int] = Array(repeating: 0, count: 26)
        for c in s {
            nlist[Int(c.asciiValue!)-97] += 1
        }
        
        // 上一个字符
        var lastC: Character? = nil
        var asciiValue = 0
        var charts: [Character] = []
        for c in s {
            asciiValue = Int(c.asciiValue!) - 97
            
            // 在：不为空 / 递增
            while charts.isEmpty == false, c < lastC!, nlist[asciiValue] > 0 {
                if nlist[Int(lastC!.asciiValue!) - 97] == 0 {  // 说明lastC只有一个，不允许删除
                    break
                } else {                // lastC在后面还有，这个可以删除了
                    charts.removeLast()
                    // 把lastC的个数变成正：表示尚未将入到结果集中
                    nlist[Int(lastC!.asciiValue!) - 97] = -nlist[Int(lastC!.asciiValue!) - 97]
                    lastC = charts.last
                }
            }
            if nlist[asciiValue] > 0 {
                charts.append(c)
                // 将个数变成负数，表示：已经加入到结果集中，后面还有 -n 个数字
                nlist[asciiValue] = -nlist[asciiValue] + 1
                lastC = c
            } else {
                // 这个字符，前面已经存储了，那么本次将次数变小
                nlist[asciiValue] += 1
            }
//            print(c, nlist, charts)
        }
        return String(charts)
    }
}
